#include<bits/stdc++.h>
using namespace std;

class Solution {
private:
    vector<int> pre, w;
    unsigned long long tot;
    int range_l(int i){return pre[i] - w[i] + 1;} 
public:
    Solution(vector<int>& w) {
        this->w = w;
        tot = 0;
        for(int i = 0; i < w.size(); i++)tot += w[i];
        pre = w;
        for(int i = 1; i < w.size(); i++)pre[i] += pre[i - 1];
        srand(unsigned(time(nullptr)));
    }
    
    int pickIndex() {
        int select = rand() % tot + 1;
        int low = 0, high = w.size() - 1;
        while(low < high){
            int temp = (low + high) / 2;
            if(range_l(temp) <= select && (temp == tot - 1 || range_l(temp + 1) > select))return temp;
            if(range_l(temp) > select)high = temp;
            else low = temp + 1;
        }
        return low;
    }
};


/**
 * 2021.8.30
 * 前缀和 + 二分查找 构建按概率选下标
 * 先求整个 w 数组的和 tot,然后可以按每个 w[i] 把 w 分成 w.size() 份。
 * 比如 w = [3, 1, 2], 那么分完以后就是{[1,3], [4,4]. [5,6]}这三份。
 * 每个 w[i] 就代表它这份的长度，然后随机在 [1, tot] 中选个数，看落在哪个 w[i] 上
 * 用二分查找的方式找回下标。
 */